package com.study;


// 基于无序数组实现
public class PriorityQueue1<E extends Priority> implements Queue<E>
{
    Priority[] array;
    int size;

    public PriorityQueue1(int capacity)
    {
        array = new Priority[capacity];
    }

    @Override
    public boolean offer(E value)
    {
        if (isFull()) return false;
        array[size++] = value;
        return true;
    }

    private void remove(int index)
    {
        if (index < 0) return;
        if (index < size - 1) {
            // 不是最后一个元素，需要把 index 后面的元素全部向前移动一下
            System.arraycopy(array, index + 1, array, index, size - 1 - index);
        }
        array[--size] = null; // help GC
    }

    @Override
    public E poll()
    {
        if (isEmpty()) {
            return null;
        }
        int max = selectMax();
        E e = (E) array[max];
        remove(max);
        return e;
    }

    // 返回最大元素的索引
    private int selectMax()
    {
        int maxIndex = 0;
        for (int i = 1; i < array.length; i++) {
            if (array[i].priority() > array[maxIndex].priority()) {
                maxIndex = i;
            }
        }
        return maxIndex;
    }

    @Override
    public E peek()
    {
        if (isEmpty()) return null;
        int maxIndex = selectMax();
        return (E) array[maxIndex];
    }

    @Override
    public boolean isEmpty()
    {
        return size == 0;
    }

    @Override
    public boolean isFull()
    {
        return size == array.length;
    }
}
